class TreeNode {
    // input your code
    key: any;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(value: any) {
        this.key = value;
        this.left = null;
        this.right = null;
    }
}

class SearchTree {
    private root!: TreeNode | null;
    private traversal: number[] = [];
    constructor() {
        this.root = null
    }

    // 添加节点
    public add(key: number) {
       // input your code
       var newNode = new TreeNode(key);
       if (this.root === null) {
           this.root = newNode;
       } else {
           this.insertNode(this.root, newNode);
       }
    }
    
    private insertNode(node: TreeNode, newNode: TreeNode) {
       // input your code
       if (newNode.key < node.key) {
           if (node.left === null) {
               node.left = newNode

           } else {
               this.insertNode(node.left, newNode)
           }
       } else {
           if (node.right === null) {
               node.right = newNode
           } else {
               this.insertNode(node.right, newNode)
           }
       }
    }

    // 查询：在二叉树查找一个键，如果节点存在，则返回 true；如果不存在，则返回 false。    
    public hasValue(value: number): boolean {
        // input your code
        while(this.root !== null) {
            if (value < this.root.key) {
                this.root = this.root.left
            } else if (value > this.root.key) {
                this.root = this.root.right
            } else {
                return true
            }
        }
        return false
    }
    
    // 升序输出
    public print() {
        // input your code
        let arr: any = []
        function printNode(node: TreeNode) {
            if (node.left) {
                printNode(node.left)
            }
            arr.push(node.key)
            // 左在前，查完左，在插入
            if (node.right) {
                printNode(node.right)
            }
        }
        if (!this.root) {
            return [];
        }
        printNode(this.root)
        return arr;
    }
    public remove(value: number) {
        // input your code
        let node: TreeNode = this.root;
        let parentNode: any = null;
        let isLeftChild: boolean = true;
        if(this.hasValue(value)){
            // 循环查找到要删除的节点 node，以及它的 parentNode（删除节点的父节点）和 isLeftChild(保存 node 是否为 parentNode 的左节点)
            while (node.key !== value) {
                parentNode = node;
                if (value < node.key) {
                isLeftChild = true;
                node = node.left;
                } else { 
                isLeftChild = false;
                node = node.right;
                }
            }
            // 1、删除的是叶子节点的情况
            if (node.left === null && node.right === null) {
                if (node === this.root) {
                this.root = null;
                } else if (isLeftChild) {
                parentNode.left = null;
                } else {
                parentNode.right = null;
                }
            // 2、删除的是只有一个子节点的节点
            } else if (node.right === null) { // currentNode 只存在左节点
                if (node === this.root) {
                this.root = node.left;
                } else if (isLeftChild) {
                parentNode.left = node.left;
                } else {
                parentNode.right = node.left;
                }
            } else if (node.left === null) { // currentNode 只存在右节点
                if (node === this.root) {
                this.root = node.right;
                } else if (isLeftChild) {
                parentNode.left = node.right;
                } else {
                parentNode.right = node.right;
                }
            // 3、删除的是有两个子节点的节点
            } else {

                // 找到后续节点
                let follow = this.getFollow(node);
            
                // 判断是否为根节点
                if (node === this.root) {
                this.root = follow;
                } else if (isLeftChild) {
                parentNode.left = follow;
                } else {
                parentNode.right = follow;
                }
            
                // 将后续的左节点改为被删除的左节点
                follow.left = node.left;
            } 
            console.log('已经删除节点:' + value);
        }else{
            console.log('不存在节点:' + value + ',请重新输入');
        }
    }
     // 获取后续节点，即从要删除的节点的右边开始查找最小的值
    public getFollow(delNode: TreeNode) {
        let follow = delNode;
        let node = delNode.right;
        let followParent = delNode;

        // 循环查找 node 的右子树节点
        while (node !== null) {
          followParent = follow;
          follow = node;
          node = node.left;
        }
    
        // 判断寻找到的后续节点是否直接就是要删除节点的 right
        if (follow !== delNode.right) {
            followParent.left = follow.right;
            follow.right = delNode.right;
        }
        return follow;
    }

}

let t = new SearchTree()
t.add(2)
t.add(4)
t.add(4)
t.add(3)
t.hasValue(2)           // true
t.print()                // 升序输出，[2, 3, 4, 4]
t.remove(3)
